剑指Offer题解 - Day23

剑指 Offer 18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

说明：

• 题目保证链表中节点的值互不相同
• 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

分析：

链表的题目，首先考虑使用双指针来解决。根据题目描述，保证了链表中节点互不相同，因此遍历节点，当遇到指定值时，进行删除处理。同时暂存链表的头部节点，方便最后返回。

还需要处理一些极端情况，如果链表为空或者头部节点是需要删除的节点等。

双指针

/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var deleteNode = function(head, val) {
    if (!head) return null; // 链表为空，返回null
    if (head.val === val) { // 头部节点就是需要删除的节点
        return head.next; // 返回头部节点的下一个节点
    }
    let pre = head; // 前驱指针指向头部
    let cur = head.next; // 当前指针指向头部节点的下一个节点
    while(cur && cur.val !== val) { // 当前节点存在并且值不与目标值相同
        pre = cur; // 前驱节点和当前节点后移一位
        cur = cur.next;
    }
    if (cur) pre.next = cur.next; // 删除当前节点
    return head; // 此时已删除相应节点，返回头部节点
};

• 时间复杂度 O(n)。
• 空间复杂度 O(1)。

总结

本题意图是删除链表中指定的节点，因此优先考虑使用双指针解决。我们声明两个指针，分别用来存放前驱节点和当前节点，记录前驱节点的目的是为了获取pre.next ，因为删除某个节点其实就是将当前节点的next赋值给前驱节点的next，核心代码就是pre.next = cur.next 。这样做之后，当再次遍历链表时，就会跳过被删除的节点，仿佛不存在过。

这里需要注意的是，要防止cur为null时，进行获取cur.val和cur.next ，所以在循环以及循环结束后，都要判断cur是否存在。 如果不存在，也就意味着链表中根本没有指定的节点，也就不需要删除，直接返回头部节点即可。

复杂度方面，由于需要遍历整个链表，因此时间复杂度是O(n) ，额外声明了两个指针，因此空间复杂度是O(1)。